package lc.q150_200;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q216 {

    public static void main(String[] args) {
        Q216 q216 = new Q216();
        List<List<Integer>> lists = q216.combinationSum3(4, 1);
        System.out.println(lists);
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        // 构建一个512大小的数组
        int[][] arr = new int[512][2];
        for (int i = 0; i < 512; i++) {
            for (int j = 0; j < 9; j++) {
                if (((1 << j) & i) != 0) {
                    // 说明该位置有数字
                    arr[i][0] = arr[i][0] + j + 1;
                    arr[i][1] ++;
                }
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        // 遍历这些数组，检测是否为k个1和等于n
        for (int i = 0; i < 512; i++) {
            if (arr[i][0] == n && arr[i][1] == k) {
                // 说明找到了,需要将i分解成位数
                List<Integer> next = new ArrayList<>();
                for (int j = 0; j < 9; j++) {
                    if (((i >> j) & 1) != 0) {
                        // 说明该位数有值
                        next.add(j + 1);
                    }
                }
                result.add(next);
            }
        }
        return result;
    }
}
